﻿using System;
using System.Collections.Generic;

namespace GX
{
    public static class ListSearch
    {
        /// <summary>
        /// 存在：返回元素所在位置
        ///不存在：返回元素插入的位置
        ///元素可能有比较结果相同的：往尾部插入
        /// </summary>
        static public bool BinarySearch<T>(List<T> list, T item, IComparer<T> comp, out int index) where T : class
        {
            int len = list.Count;
            int L = 0;
            int H = len - 1;

            int pos = -1;
            int compareValue = 1;

            T cur;
            while (L <= H)
            {
                pos = (L + H) / 2;
                cur = list[pos];
                
                if (ReferenceEquals(cur, item))
                {
                    index = pos;
                    return true;
                }
                compareValue = comp.Compare(item, cur);
                if (0 == compareValue || L == H)
                    break;
                if (compareValue > 0)
                    L = pos + 1;
                else
                    H = pos - 1;
            }
            if (compareValue == 0)
            {
                int i = pos - 1;
                for (; i >= L; --i)
                {
                    cur = list[i];
                    if (ReferenceEquals(cur,item))
                    {
                        index = pos;
                        return true;
                    }
                    compareValue = comp.Compare(item, cur);
                    if (0 != compareValue)
                        break;
                }
                for (i = pos + 1; i <= H; ++i)
                {
                    cur = list[i];
                    if (ReferenceEquals(cur, item))
                    {
                        index = pos;
                        return true;
                    }
                    compareValue = comp.Compare(item, cur);
                    if (0 == compareValue)
                        pos = i;
                    else
                        break;
                }
            }
            if (compareValue >= 0)
                index = pos + 1;
            else
                index = pos;
            return false;
        }
        /// <summary>
        ///存在：返回元素所在位置
        ///不存在：返回元素插入的位置
        /// </summary>
        /// <param name="returnFirst">为true返回第一个，否则最后一个</param>
        /// <returns></returns>
        static public bool BinarySearch(List<int> list, int item, out int index,bool returnFirst=true,bool reverse=false)
        {
            int len = list.Count;
            int L = 0;
            int H = len - 1;

            int pos = -1;
            int compareValue = 1;

            int cur;
            while (L <= H)
            {
                pos = (L + H) / 2;
                cur = list[pos];
                if (item == cur)
                {
                    compareValue = 0;
                    if (returnFirst)
                    {
                        index = pos;
                        return true;
                    }
                    break;
                }
                compareValue = item < cur ? (reverse ? 1 : -1) : (reverse ? -1 : 1);
                
                if (L == H)
                    break;
                if (compareValue > 0)
                    L = pos + 1;
                else
                    H = pos - 1;
            }
            if (compareValue == 0)
            {
                for (int i = pos + 1; i <= H; ++i)
                {
                    cur = list[i];
                    if (cur == item)
                        pos = i;
                    else
                        break;
                }
                index = pos;
                return true;
            }
            if (compareValue > 0)
                index = pos + 1;
            else
                index = pos;
            return false;
        }
    }
}
